/**
|--------------------------------------------------
| 有 n 个气球，编号为0 到 n - 1，每个气球上都标有一个数字，
这些数字存在数组 nums 中。

现在要求你戳破所有的气球。戳破第 i 个气球，

你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。

 这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。

如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。

求所能获得硬币的最大数量。
输入：nums = [3,1,5,8]
输出：167
解释：
nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
coins =  3*1*5    +   3*5*8   +  1*3*8  + 1*8*1 = 167
输入：nums = [1,5]
输出：10
1 1*5*1 = 5
5 1*5*1 = 5
5_+5 = 10
输入：nums = [3,1,5]
输出：35
3*1*5 = 15
1*3*5 = 15
1*5*1 = 5
15+15+ 5 = 35 
思路是最后一步做了什么

|--------------------------------------------------
*/
var maxCoins = function (nums) {
  if (nums == null || nums.length === 0) return 0
  // 为什么+2 [+1,3,2,4,+1] 前后加个1
  let n = nums.length
  nums.unshift(1)
  nums.push(1)
  //初始化dp
  let dp = new Array(nums.length)
    .fill(0)
    .map(() => new Array(nums.length).fill(0))
  //遍历
  for (let len = 1; len <= n; len++) {
    for (let i = 1; i <= n - len + 1; i++) {
      //计算循环停止条件
      let j = i + len - 1
      //nums[i - 1] * nums[k] * nums[j + 1] 代表 前 + 当前 + 后  [1,3,5]
      // 正确的顺序应该是先遍历完所有长度为1的区间，再是长度为2的区间，再依次累加长度，直到最后才遍历整个区间：
      // [3] -> [1] -> [5] -> [8] -> [3, 1] -> [1, 5] -> [5, 8] -> [3, 1, 5] -> [1, 5, 8] -> [3, 1, 5, 8]
      for (let k = i; k <= j; k++) {
        // 状态转移方程
        //  区间[i, k-1]，[k]，和 [k+1, j]
        /*
        |--------------------------------------------------
        ! 周围两个气球被 nums[k-1] * nums[k] * nums[k+1]，但其实这样是错误的，为啥呢？
        ? dp[i][k-1] 的意义是什么呢，是打爆区间 [i, k-1] 内所有的气球后的最大得分，
        * 此时第 k-1 个气球已经不能用了，同理，第 k+1 个气球也不能用了相当于区间 [i, j] 中除了第k个气球，其他的已经爆了，
        * 那么周围的气球只能是第 i-1 个和第 j+1 个了，所以得分应为 nums[i-1] * nums[k] * nums[j+1]
        |--------------------------------------------------
        */
        dp[i][j] = Math.max(
          dp[i][j],
          nums[i - 1] * nums[k] * nums[j + 1] + dp[i][k - 1] + dp[k + 1][j]
        )
      }
    }
  }
  console.log('dp', dp)
  return dp[1][n]
}

console.log('maxCoins', maxCoins([1, 5]))
console.log('maxCoins', maxCoins([1, 3, 5]))
